--[[
    完全二叉树的大小堆实现
    参考：https://www.cnblogs.com/ssyfj/p/9512451.html
    node = {
        id 作为大小比较值
    }
--]]

local table_insert = table.insert
local table_remove = table.remove

local Heap = {}

function Heap.new(...)
    local instance = setmetatable({}, {__index=Heap})
    instance:ctor(...)
    return instance
end

function Heap:ctor()
    self.nodes = {} --用于存放数据
end

--队列的方式实现, 每次插入都要遍历列表查找
function Heap:push(node)
    table_insert(self.nodes, node)
    return
end

function Heap:pop()
    if not self.nodes or not self.nodes[1] then
        return
    end
    local value = self.nodes[1]
    table_remove(self.nodes, 1)
    return value
end

function Heap:getNodes()
    return self.nodes
end

function Heap:print()
    for i = 1, #self.nodes do
        print(i, self.nodes[i].id)
    end
end

function Heap:size()
    return #self.nodes
end

function Heap:clear()
    self.nodes = {} --用于存放数据
end


--最大堆
--i*2 是左节点的下标
--i*2+1 是右下节点的下标
function Heap:maxHeap(nodes)
    if not nodes then
        nodes = self.nodes
    end
    local n = #nodes
    --n/2 是最后一个非叶子节点到第1个节点向下调整
    local last = math.floor(n/2)
    for i=last, 1, -1 do
        self:bigSiftdown(nodes, i, n)
    end
end


--最小堆
--i*2 是左节点的下标
--i*2+1 是右下节点的下标
function Heap:minHeap(nodes)
    if not nodes then
        nodes = self.nodes
    end
    local n = #nodes
    --self.n/2 是最后一个非叶子节点到第1个节点向下调整
    local last = math.floor(n/2)
    for i=last, 1, -1 do
        self:minSiftdown(nodes, i, n)
    end
end

--大堆使用
function Heap:bigSiftdown(nodes, i, n)
    if not nodes then
        nodes = self.nodes
    end
    local move = true --是否向下调整
    while(i*2 <= n and move) do
        local t = nil
        local id = nodes[i].id
        local left_node = nodes[i*2]
        if left_node.id > id then
            t = i*2
        else
            t = i
        end
        local right_node = nodes[i*2+1]
        if i*2 + 1 <= n and right_node then
            --右节点
            if right_node.id > nodes[t].id then
                t = i*2+1
            end
        end
        if i ~= t then
            --交换节点
            self:swap(nodes, i, t)
            i = t --更换序号让检查继续
        else
            move = false
        end
    end
end

--小堆使用
function Heap:minSiftdown(nodes, i, n)
    if not nodes then
        nodes = self.nodes
    end
    local move = true --是否向下调整
    while(i*2 <= n and move) do
        local t = nil
        local id = nodes[i].id
        local left_node = nodes[i*2]
        if left_node.id < id then
            t = i*2
        else
            t = i
        end
        local right_node = nodes[i*2+1]
        if i*2 + 1 <= n and right_node then
            --右节点
            if right_node.id < nodes[t].id then
                t = i*2+1
            end
        end
        if i ~= t then
            --交换节点
            self:swap(nodes, i, t)
            i = t --更换序号让检查继续
        else
            move = false
        end
    end
end

--[[
1.将长度为n的待排序的数组进行堆有序化构造成一个大顶堆
2.将根节点与尾节点交换并输出此时的尾节点
3.将剩余的n -1个节点重新进行堆有序化
4.重复步骤2，步骤3直至构造成一个有序序列

构造堆的时间复杂度为O(n)
重建堆时时间复杂度为O(nlogn)。
所以总体就是O(nlogn)。
不适合排序序列个数较少的情况
--]]
function Heap:heapSort(nodes)
    --从小到大， 用最大堆
    if not nodes then
        nodes = self.nodes
    end

    local len = #nodes
    while len > 1  do
        --第1个与最后一个交换
        self:swap(nodes, 1, len)
        len = len - 1
        self:bigSiftdown(nodes,1, len) --第1个节点往下调整
    end
end

function Heap:swap(tb, a, b)
    local tmp = tb[a]
    tb[a] = tb[b]
    tb[b] = tmp
end
------------------------------------------------------------------
--测试
------------------------------------------------------------------
if arg and arg[0] == "heap.lua" then
    local queue = Heap.new()
    queue:push({id=2})
    queue:push({id=12})
    queue:push({id=1})
    queue:push({id=8})
    queue:push({id=6})
    queue:push({id=5})
    queue:push({id=6})
    queue:push({id=16})
    queue:push({id=6})
    queue:maxHeap()
    queue:print()
    print("_______")

    print("_______sort")
    queue:heapSort()
    queue:print()

    local a = queue:pop()
    queue:minHeap()
    --local b = queue:pop()
    --print("pop:", a, b)
    print("_______")

    queue:print()


end

return Heap